package backTracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author pengfei.hpf
 * @date 2020/3/4
 * @verdion 1.0.0
 */
public class SolveNQueens {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        if(n == 0){
            return res;
        }
        char[][] board = new char[n][n];
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j++){
                board[i][j] = '.';
            }
        }
        backtrace(n, 0, board);
        return res;
    }

    private void backtrace(int n, int row, char[][] board){
        if(row == n){
            List<String> path = new ArrayList<>();
            for(char[] chars: board){
                path.add(new String(chars));
            }
            res.add(path);
            return;
        }

        for(int i = 0; i < n; i ++){
            if(isValid(board, row, i)){
                board[row][i] = 'Q';
                backtrace(n, row + 1, board);
                board[row][i] = '.';
            }
        }

    }

    private boolean isValid(char[][] board, int row, int col){
        for(int i = 0; i < row; i ++){
            if(board[i][col] == 'Q'){
                return false;
            }
        }

        for(int i = row -1, j = col +1; i >= 0 && j < board.length; i --, j++){
            if(board[i][j] == 'Q'){
                return false;
            }
        }

        for(int i = row -1, j = col -1; i >= 0 && j >= 0; i --, j --){
            if(board[i][j] == 'Q'){
                return false;
            }
        }

        return true;
    }
}
